package com.barry.algorithm.graph;

import java.util.*;

/**
 * 类功能描述：//TODO
 *
 * @author BarryWang create at 19-9-8 下午10:08
 * @version 1.0.0
 */
public class Graph {
    private int[] mVexs;       // 顶点集合
    private int[][] mMatrix;    // 邻接矩阵

    /*
     * create the graph
     */
    public Graph() {
        System.out.printf("Please input the Graph: ");
        String graph = readString();
        String[] allEdge = graph.split(",");
        Set allVertex = new TreeSet();
        for(String meta: allEdge){
            String edge = meta.trim();
            if(edge.length() < 3){
                System.out.println("Please input the valid edge");
                return;
            }
            char begin = edge.charAt(0);
            char end = edge.charAt(1);
            String weight = edge.substring(2);
            if(begin < 'A' || begin > 'Z' ||  end < 'A' || end > 'Z'){
                System.out.println("Please input the valid vertex");
                return;
            }
            char[] weigtArray = weight.toCharArray();
            for(char item : weigtArray){
                if(item < '0' || item > '9'){
                    System.out.println("Please input the valid weight");
                    return;
                }
            }
            allVertex.add(begin);
            allVertex.add(end);
        }

        int vlen = allVertex.size();
        int elen = allEdge.length;
        if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
            System.out.printf("input error: invalid parameters!\n");
            return ;
        }

        //init the vertex
        mVexs = new int[vlen];
        Object[] allV = allVertex.toArray();
        for (int i = 0; i < vlen; i++) {
            mVexs[i] = ((Character)allV[i]).charValue();
        }

        //init the edge
        mMatrix = new int[vlen][vlen];
        for(String meta: allEdge) {
            String edge = meta.trim();
            char begin = edge.charAt(0);
            char end = edge.charAt(1);
            int weight = Integer.parseInt(edge.substring(2));
            int p1 = getPosition(begin);
            int p2 = getPosition(end);
            mMatrix[p1][p2] = weight;
        }
    }


    /**
     * 寻找起点到终点的所有路径
     *
     * @param goal
     *            目标
     * @param stack
     */
    private void dfsStack(int goal, Stack<Integer> stack, List list) {
        if (stack.isEmpty()) {
            return;
        }
        // 访问栈顶元素，但不弹出
        int k = stack.peek().intValue();
        // 对栈顶的邻接点依次递归调用，进行深度遍历
        for (int i = 0; i < mVexs.length; i++) {
            // 有边，并且不在左上到右下的中心线上
            if (this.mMatrix[k][i] > 0 && k != i) {
                // 打印路径
                if (i == goal) {
                   /* System.out.print("\n路径:");
                    this.printStack(stack, i);*/
                    if(stack.size() <= 3){
                        list.add(1);
                    }
                    continue;
                }
                if(!stack.contains(i)){
                    // 深度遍历
                    stack.push(i);
                    dfsStack(goal, stack, list);
                }
            }
        }

        stack.pop();
    }

    /**
     * 寻找起点到终点的所有路径
     *
     * @param goal
     *            目标
     * @param stack
     */
    private void dfsStack2(int goal, Stack<Integer> stack, List list) {
        if (stack.isEmpty()) {
            return;
        }
        // 访问栈顶元素，但不弹出
        int k = stack.peek().intValue();
        // 对栈顶的邻接点依次递归调用，进行深度遍历
        for (int i = 0; i < mVexs.length; i++) {
            // 有边，并且不在左上到右下的中心线上
            if (this.mMatrix[k][i] > 0 && k != i) {
                // 打印路径
                if (i == goal) {
//                    System.out.print("\n路径:");
//                    this.printStack(stack, i);
                    if(stack.size() == 4){
                        list.add(1);
                    }
                }
                if(!stack.contains(i)) {
                    // 深度遍历
                    stack.push(i);
                    dfsStack2(goal, stack, list);
                }
            }
        }

        stack.pop();
    }

    /**
     * 寻找起点到终点的所有路径
     *
     * @param goal
     *            目标
     * @param stack
     */
    private void dfsWeight(int goal, Stack<Integer> stack, Set set) {
        if (stack.isEmpty()) {
            return;
        }
        // 访问栈顶元素，但不弹出
        int k = stack.peek().intValue();
        // 对栈顶的邻接点依次递归调用，进行深度遍历
        for (int i = 0; i < mVexs.length; i++) {
            // 有边，并且不在左上到右下的中心线上
            if (this.mMatrix[k][i] > 0 && k != i) {
                // 打印路径
                if (i == goal) {
                    set.add(getWeight(stack, i));
                    continue;
                }
                if(!stack.contains(i)) {
                    // 深度遍历
                    stack.push(i);
                    dfsWeight(goal, stack, set);
                }
            }
        }

        stack.pop();
    }

    private int getWeight(Stack<Integer> stack, int k) {
        List<Integer> items = new ArrayList<>();
        for (int i : stack) {
            items.add(mVexs[i]);
        }
        items.add(mVexs[k]);
        int weight = 0;
        for(int i=items.size()-1; i>0; i--){
            weight = weight+disOfRoute((char)items.get(i-1).intValue(), (char)items.get(i).intValue());
        }
        return weight;
    }

    private void printStack(Stack<Integer> stack, int k) {
        for (Integer i : stack) {
            System.out.print((char)this.mVexs[i] + ",");
        }
        System.out.print((char)this.mVexs[k]);
    }


    /**
     * cal the distance of one edge
     */
    public int disOfRoute(char a0, char b0){
        int a = getPosition(a0);
        int b = getPosition(b0);
        return mMatrix[a][b];
    }

    public String distanceOfRoute1(){
        int ab = disOfRoute('A', 'B');
        if(ab == 0){
            return "NO SUCH ROUTE";
        }
        int bc = disOfRoute('B', 'C');
        if(bc == 0){
            return "NO SUCH ROUTE";
        }
        return (ab+bc)+"";
    }

    public String distanceOfRoute2(){
        int ad = disOfRoute('A', 'D');
        if(ad == 0){
            return "NO SUCH ROUTE";
        }
        return ad+"";
    }

    public String distanceOfRoute3(){
        int ad = disOfRoute('A', 'D');
        if(ad == 0){
            return "NO SUCH ROUTE";
        }
        int dc = disOfRoute('D', 'C');
        if(dc == 0){
            return "NO SUCH ROUTE";
        }
        return (ad+dc)+"";
    }

    public String distanceOfRoute4(){
        int ae = disOfRoute('A', 'E');
        if(ae == 0){
            return "NO SUCH ROUTE";
        }
        int eb = disOfRoute('E', 'B');
        if(eb == 0){
            return "NO SUCH ROUTE";
        }
        int bc = disOfRoute('B', 'C');
        if(bc == 0){
            return "NO SUCH ROUTE";
        }
        int cd = disOfRoute('C', 'D');
        if(cd == 0){
            return "NO SUCH ROUTE";
        }
        return (ae+eb+bc+cd)+"";
    }

    public String distanceOfRoute5(){
        int ae = disOfRoute('A', 'E');
        if(ae == 0){
            return "NO SUCH ROUTE";
        }
        int ed = disOfRoute('E', 'D');
        if(ed == 0){
            return "NO SUCH ROUTE";
        }
        return (ae+ed)+"";
    }

    /*
     * return the char position
     */
    private int getPosition(char ch) {
        for(int i=0; i<mVexs.length; i++)
            if(mVexs[i]==ch)
                return i;
        return -1;
    }

    private String readString() {
        Scanner scanner = new Scanner(System.in);
        return scanner.nextLine();
    }

    /*
     * print the graph
     */
    public void print() {
        System.out.printf("Martix Graph:\n");
        for (int i = 0; i < mVexs.length; i++) {
            for (int j = 0; j < mVexs.length; j++)
                System.out.printf("%d ", mMatrix[i][j]);
            System.out.printf("\n");
        }
    }

    public static void main(String[] args) {
        Graph pG = new Graph();
        pG.print();   // 打印图
        System.out.println("Output #1:"+pG.distanceOfRoute1());
        System.out.println("Output #2:"+pG.distanceOfRoute2());
        System.out.println("Output #3:"+pG.distanceOfRoute3());
        System.out.println("Output #4:"+pG.distanceOfRoute4());
        System.out.println("Output #5:"+pG.distanceOfRoute5());

        int origin = 2;
        int goal = 2;
        List<Integer> countList = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<>();
        stack.push(origin);
        pG.dfsStack(goal, stack, countList);
        System.out.println("Output #6:"+countList.size());

        int origin2 = 0;
        int goal2 = 2;
        List<Integer> countList2 = new ArrayList<Integer>();
        Stack<Integer> stack2 = new Stack<>();
        stack2.push(origin2);
        pG.dfsStack2(goal2, stack2, countList2);
        System.out.println("Output #7:"+countList2.size());

        int origin3 = 0;
        int goal3 = 2;
        Set<Integer> weight3 = new TreeSet<>();
        Stack<Integer> stack3 = new Stack<>();
        stack3.push(origin3);
        pG.dfsWeight(goal3, stack3, weight3);
        System.out.println("Output #8:"+((TreeSet<Integer>) weight3).first());

        int origin4 = 1;
        int goal4 = 1;
        Set<Integer> weight4 = new TreeSet<>();
        Stack<Integer> stack4 = new Stack<>();
        stack4.push(origin4);
        pG.dfsWeight(goal4, stack4, weight4);
        System.out.println("Output #9:"+((TreeSet<Integer>) weight4).first());

        int origin5 = 1;
        int goal5 = 1;
        Set<Integer> weight5 = new TreeSet<>();
        Stack<Integer> stack5 = new Stack<>();
        stack5.push(origin5);
        pG.dfsWeight(goal5, stack5, weight5);
        int count = 0;
        for(int meta : weight5){
            if(meta <= 30){
                count++;
            }
        }
        System.out.println("Output #10:"+count);
    }
}
